A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by an m x n grid of characters grid where each element is a wall, floor, or box.
Your task is to move the box 'B' to the target position 'T' under the following rules:
- The character
'S'represents the player. The player can move up, down, left, right ingridif it is a floor (empty cell). - The character
'.'represents the floor which means a free cell to walk. - The character
'#'represents the wall which means an obstacle (impossible to walk there). - There is only one box
'B'and one target cell'T'in thegrid. - The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
- The player cannot walk through the box.
Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.
Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 3 Explanation: We return only the number of times the box is pushed.
Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#","#","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: -1
Input: grid = [["#","#","#","#","#","#"], ["#","T",".",".","#","#"], ["#",".","#","B",".","#"], ["#",".",".",".",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 5 Explanation: push the box down, left, left, up and up.
m == grid.lengthn == grid[i].length1 <= m, n <= 20gridcontains only characters'.','#','S','T', or'B'.- There is only one character
'S','B', and'T'in thegrid.
use std::collections::HashSet;use std::collections::VecDeque;implSolution{pubfnmin_push_box(grid:Vec<Vec<char>>) -> i32{let(m, n) = (grid.len(), grid[0].len());letmut visited_player = HashSet::new();letmut stack_player = vec![];letmut visited_box = HashSet::new();letmut deque_box = VecDeque::new();for i in0..m {for j in0..n {if grid[i][j] == 'S'{ visited_player.insert((i, j)); stack_player.push((i, j));break;}}}whileletSome((i, j)) = stack_player.pop(){if i > 0 && grid[i - 1][j] == 'B' && !visited_box.contains(&(i - 1, j,'U')){ visited_box.insert((i - 1, j,'U')); deque_box.push_back((i - 1, j,'U',0));}if i < m - 1 && grid[i + 1][j] == 'B' && !visited_box.contains(&(i + 1, j,'D')){ visited_box.insert((i + 1, j,'D')); deque_box.push_back((i + 1, j,'D',0));}if j > 0 && grid[i][j - 1] == 'B' && !visited_box.contains(&(i, j - 1,'L')){ visited_box.insert((i, j - 1,'L')); deque_box.push_back((i, j - 1,'L',0));}if j < n - 1 && grid[i][j + 1] == 'B' && !visited_box.contains(&(i, j + 1,'R')){ visited_box.insert((i, j + 1,'R')); deque_box.push_back((i, j + 1,'R',0));}if i > 0 && grid[i - 1][j] != '#' && grid[i - 1][j] != 'B' && !visited_player.contains(&(i - 1, j)){ visited_player.insert((i - 1, j)); stack_player.push((i - 1, j));}if i < m - 1 && grid[i + 1][j] != '#' && grid[i + 1][j] != 'B' && !visited_player.contains(&(i + 1, j)){ visited_player.insert((i + 1, j)); stack_player.push((i + 1, j));}if j > 0 && grid[i][j - 1] != '#' && grid[i][j - 1] != 'B' && !visited_player.contains(&(i, j - 1)){ visited_player.insert((i, j - 1)); stack_player.push((i, j - 1));}if j < n - 1 && grid[i][j + 1] != '#' && grid[i][j + 1] != 'B' && !visited_player.contains(&(i, j + 1)){ visited_player.insert((i, j + 1)); stack_player.push((i, j + 1));}}whileletSome((i, j, s, pushes)) = deque_box.pop_front(){if grid[i][j] == 'T'{return pushes;}letmut bi = i;letmut bj = j;if s == 'U' && i > 0 && grid[i - 1][j] != '#'{ bi -= 1;}elseif s == 'D' && i < m - 1 && grid[i + 1][j] != '#'{ bi += 1;}elseif s == 'L' && j > 0 && grid[i][j - 1] != '#'{ bj -= 1;}elseif s == 'R' && j < n - 1 && grid[i][j + 1] != '#'{ bj += 1;}else{continue;} visited_player = HashSet::from([(i, j)]); stack_player = vec![(i, j)];whileletSome((i, j)) = stack_player.pop(){if i > 0 && i - 1 == bi && j == bj && !visited_box.contains(&(bi, bj,'U')){ visited_box.insert((bi, bj,'U')); deque_box.push_back((bi, bj,'U', pushes + 1));}if i < m - 1 && i + 1 == bi && j == bj && !visited_box.contains(&(bi, bj,'D')){ visited_box.insert((bi, bj,'D')); deque_box.push_back((bi, bj,'D', pushes + 1));}if j > 0 && i == bi && j - 1 == bj && !visited_box.contains(&(bi, bj,'L')){ visited_box.insert((bi, bj,'L')); deque_box.push_back((bi, bj,'L', pushes + 1));}if j < n - 1 && i == bi && j + 1 == bj && !visited_box.contains(&(bi, bj,'R')){ visited_box.insert((bi, bj,'R')); deque_box.push_back((bi, bj,'R', pushes + 1));}if i > 0 && grid[i - 1][j] != '#' && (i - 1 != bi || j != bj) && !visited_player.contains(&(i - 1, j)){ visited_player.insert((i - 1, j)); stack_player.push((i - 1, j));}if i < m - 1 && grid[i + 1][j] != '#' && (i + 1 != bi || j != bj) && !visited_player.contains(&(i + 1, j)){ visited_player.insert((i + 1, j)); stack_player.push((i + 1, j));}if j > 0 && grid[i][j - 1] != '#' && (i != bi || j - 1 != bj) && !visited_player.contains(&(i, j - 1)){ visited_player.insert((i, j - 1)); stack_player.push((i, j - 1));}if j < n - 1 && grid[i][j + 1] != '#' && (i != bi || j + 1 != bj) && !visited_player.contains(&(i, j + 1)){ visited_player.insert((i, j + 1)); stack_player.push((i, j + 1));}}} -1}}